package dfs;

import java.util.HashSet;
import java.util.Set;

public class 活字印刷 {

    public int numTilePossibilities(String tiles) {
        boolean[] booleans = new boolean[tiles.length()];
        Set<String> set = new HashSet<>();
        dfs(booleans,set,tiles,new StringBuilder());
        return set.size()-1;
    }

    private void dfs(boolean[] booleans, Set<String> set, String tiles, StringBuilder builder) {
        set.add(builder.toString());
        for (int i = 0; i < tiles.length(); i++) {
            if (!booleans[i]){
                booleans[i]=true;
                builder.append(tiles.charAt(i));
                dfs(booleans,set,tiles,builder);
                builder.deleteCharAt(builder.length()-1);
                booleans[i]=false;
            }
        }
    }
}
